/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-13
 * Time: 22:42
 */

/**
 * 分割链表：
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。

 * 示例 1：
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * 示例 2：
 *
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 */
public class Exercise1 {

    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode partition(ListNode head, int x) {
        //定义两个链表
        ListNode head1 = new ListNode(0);
        ListNode head2 = new ListNode(0);

        ListNode node1 = head1;
        ListNode node2 = head2;
        //找出大于x和小于x的两个链表
        while(head != null) {
            if(head.val < x ){
                node1.next = head;
                node1 = node1.next;
            }else {
                node2.next = head;
                node2 = node2.next;
            }
            head = head.next;
        }
        //拼接两个链表
        node1.next = head2.next;
        node2.next = null;

        return head1.next;
    }
}
